
/// 定义一个fib的宏
macro_rules! recurrence {
    (@unit $x:tt) => { () };
    (@count $($key:tt),*) => { <[()]>::len(&[$(recurrence!(@unit $key)),*])};

    ( $seq:ident[$ind:ident]: $ty:ty = $($inits:expr),+; ... ; $recur:expr ) => {
        {
            use std::ops::Index;

            const MEM_SIZE: usize = recurrence!(@count $($inits),+);

            struct Recurrence {
                mem: [$ty; MEM_SIZE],
                pos: usize,
            }

            impl Iterator for Recurrence {

                type Item = $ty;

                fn next(&mut self) -> Option<Self::Item> {
                    if self.pos < MEM_SIZE {
                        let next_val = self.mem[self.pos];
                        self.pos += 1;
                        Some(next_val)
                    } else {
                        let next_val = {
                            let $ind = self.pos;
                            let $seq = IndexOffset { slice: &self.mem, offset: $ind };
                            // (a[n-1] + a[n-2])
                            $recur
                        };

                        {
                            use std::mem::swap;

                            let mut swap_tmp = next_val;
                            for i in (0..MEM_SIZE).rev() {
                                swap(&mut swap_tmp, &mut self.mem[i]);
                            }
                        }
                        self.pos += 1;
                        Some(next_val)
                    }
                }
            }

            struct IndexOffset<'a> {
                slice: &'a [$ty; MEM_SIZE],
                offset: usize,
            }

            impl <'a> Index<usize> for IndexOffset<'a> {
                type Output = $ty;

                fn index(&self, index: usize) -> &'a Self::Output {
                    use std::num::Wrapping;

                    let index = Wrapping(index);
                    let offset = Wrapping(self.offset);
                    let window = Wrapping(MEM_SIZE);

                    let real_index = index - offset + window;
                    &self.slice[real_index.0]
                }
            }

            Recurrence {mem: [$($inits),+], pos: 0}
        };
    };
}


#[cfg(test)]
mod tests {
    // 实战Fibonacci 数列

    #[test]
    fn test_fib() {
        let fib = recurrence![a[n]: u64 = 0, 1; ...; a[n-1] + a[n-2]];
        println!("fib mem len = {}", fib.mem.len());
        for (i, e) in fib.take(50).enumerate() { println!("{} - {}", i , e) }

        let fib = recurrence![f[i]: f64 = 1.0; ...; f[i-1] * i as f64];
        println!("fib mem len = {}", fib.mem.len());
        for (i, e) in fib.take(10).enumerate() { println!("{} - {}", i , e) }
    }
}

